/**
 * 33. 搜索旋转排序数组
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 */

/**
 * @param {number} i
 * @param {number} offset
 * @param {number} length
 * @return {number}
 */
function realIndex(i, offset, length) {
  return (i + offset) % length;
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function search(nums, target) {
  const { length } = nums;
  let offset = 1;
  for (; offset < length; offset += 1) {
    if (nums[offset] < nums[offset - 1]) {
      break;
    }
  }
  if (offset >= length) {
    offset = 0;
  }
  let left = 0;
  let right = length - 1;
  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    const middleRealIndex = realIndex(middle, offset, length);
    const middleValue = nums[middleRealIndex];
    if (target === middleValue) return middleRealIndex;
    if (target < middleValue) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return -1;
}

console.log(search([4, 5, 6, 7, 0, 1, 2], 0) === 4);
console.log(search([4, 5, 6, 7, 0, 1, 2], 3) === -1);
console.log(search([1], 0) === -1);
